<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        function TreeNode(val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
        // a是根节点
        var a = new TreeNode(4);
        var b = new TreeNode(2);
        var c = new TreeNode(7);
        var f = new TreeNode(1);
        var g = new TreeNode(3);
        var h = new TreeNode(null);

        a.left = b;
        a.right = c;
        b.left = f;
        b.right = g;

        // 二叉树的特点: 二分查找的思想 右子树都比根节点大 左子树都比根节点小 
        // 逻辑 如果插入的值大于当前节点，就去右子树继续递归，反之，左子树
        //      如果递归式，当前节点是null 就直接创建一个新的节点
        // 时间：O(n) 最差是 链式的二叉树
        // 空间: O(n) 递归调用栈的调用情况
        // 声明一个值 记得上一个节点 parent


        // 二叉树的特点: 二分查找的思想 右子树都比根节点大 左子树都比根节点小 
        // 逻辑
        // 1. 递归遍历树
        // 2. 如果插入的值大于当前节点的值 递归遍历右子树
        // 2.1 如果右节点有值 再次递归
        // 2.2 如果是null 创建新的节点
        // 3. 如果插入的值小于当前节点的值 递归遍历左子树
        // 3.1 左子树有值 再次递归
        // 3.2 如果是null 创建新的节点
        // 4. 如果等于左子树或者是右子树，=> 不管是左边还是右边的位置都可以
        // 4.1 补充一句 如果说正好等于当前节点的值 目的是插入左子节点
        // 4.2 要先判断左节点有没有值，如果有 再次递归
        // 4.3 如果没有直接 root.left = val
        // 5. 如果插入的节点是初始化了的 直接 root.val = val
        // 6. 如果插入的节点是null 没有 new TreeNode()
        var insertIntoBST = function (root, val) {
            // 递归函数
            function set(root, val) {
                // 1. 退出条件 如果插入的节点是空值
                if (!root.val) {
                    root = new TreeNode(val)
                } else if (root.val === null) {
                    // 2. 如果插入的节点的值等于控制
                    root.val = val
                } else if (root.val < val) {
                    // 3. 插入的节点值 小于当前节点的值
                    if (root.right) {
                        set(root.right, val)
                    } else {
                        root.right = new TreeNode(val)
                    }
                } else if (root.val > val) {
                    // 4. 插入的节点的值 大于当前节点的值
                    if (root.left) {
                        set(root.left, val)
                    } else {
                        root.left = new TreeNode(val)
                    }
                } else if (root.val === val) {
                    // 5. 插入的节点的值 大于当前节点的值
                    if (root.left) {
                        set(root.left, val)
                    } else {
                        root.left = new TreeNode(val)
                    }
                }
                return root
            }
            return set(root, val)
        };
        console.log(insertIntoBST(h, 5)) // 有节点 但是val是null的情况
    </script>
</body>

</html>